package com.xk._03真题骗._01数组_排序;

import java.util.Arrays;

/*
 * @description: https://leetcode.cn/problems/sort-colors/
 * @author: xu
 * @date: 2022/10/27 5:48
 */
public class _75颜色分类 {
    public static void main(String[] args) {
        int[] nums = new int[]{2,0,2,1,1,0};
        System.out.println(Arrays.toString(nums));
        new _75颜色分类().sortColors(nums);
        System.out.println(Arrays.toString(nums));
    }

    // [2,0,2,1,1,0] --> [0,0,1,1,2,2]
    // 要求：时间复杂度：O(n) 空间复杂度：O(1)
    public void sortColors(int[] nums) {
        int left = 0, right = nums.length - 1;
        int i = 0;
        while (i <= right) {
            int value = nums[i];
            if (value == 0) {
                swap(nums, i++, left++);
            } else if (value == 2) {
                swap(nums, i, right--);
            } else { // value == 1
                i++;
            }
        }
    }

    private void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
